0% completed
Problem Statement
Given a non-negative integer num, return the maximum number, which you can create by swapping any two digits of the number only once. If no swaps can improve the number, return the original number.
Examples
-
Example 1:
- Input:
2736 - Expected Output:
7236 - Justification: Swapping the first and second digits (
2and7) results in the largest possible number.
- Input:
-
Example 2:
- Input:
9965 - Expected Output:
9965 - Justification: The number is already in its maximum form, so no swap is needed.
- Input:
-
Example 3:
- Input:
7281912 - Expected Output:
9281712 - Justification: Swapping the first digit (
7) with the first9found from the left results in the maximum number.
- Input:
Solution
To solve this problem, the approach revolves around identifying the most significant digit that can be increased by a swap. We traverse the number from right to left, identifying the largest digit seen so far and its index. This is because a larger digit appearing later in the number, when swapped with a smaller digit to its left, will yield a greater value. The key is to find the leftmost digit for which a larger digit exists anywhere to its right. Swapping these two digits will result in the maximum possible number. This approach is effective as it minimizes the swaps and ensures the largest digit possible in the highest place value.
Step-by-Step Algorithm
-
Convert the given number into an array of its digits for easier manipulation.
-
Prepare the
maxIndexAfterArray:- Initialize an array
maxIndexAfterto record the index of the maximum digit found to the right of each digit (including itself). - Traverse the digit array from right to left.
- Update
maxIndexAfterfor each position with the index of the largest digit seen so far.
- Initialize an array
-
Perform the Swap:
- Traverse the
digitsarray from left to right. - If
digits[i]anddigits[maxIndexAfter[i]]are not same, swap both elements. - After the first swap, break the loop.
- Traverse the
-
Reconstruct the Number: Convert the digit array back into a single integer.
-
Return the Result: Provide the modified number as the output.
Algorithm Walkthrough
Consider the Input 7281912.
-
Initialization:
- Convert to digit array:
[7, 2, 8, 1, 9, 1, 2]. - Initialize
maxIndexAfterarray with the same length as the digit array.
- Convert to digit array:
-
Preparing the
maxIndexAfterArray:- Start from the rightmost digit.
- Iteration 1 (Index 6): Digit
2,maxIndexAfter[6] = 6. - Iteration 2 (Index 5): Digit
1,maxIndexAfter[5] = 6(as2is the maximum seen so far). - Iteration 3 (Index 4): Digit
9,maxIndexAfter[4] = 4. - Continue updating
maxIndexAfterfor each digit. - Final
maxIndexAfterarray:[4, 4, 4, 4, 4, 6, 6].
-
Performing the Swap:
- Traverse from left to right.
- Iteration 1 (Index 0): Digit
7, compare withmaxIndexAfter[0](digit at index 4 which is9), so swap them. - As soon as the first swap opportunity is found, break the loop.
- Array after swap:
[9, 2, 8, 1, 7, 1, 2].
-
Reconstructing the Number:
- Convert array back to number:
9281712.
- Convert array back to number:
-
Returning the Result:
- Return
9281712.
- Return
Code
Complexity Analysis
Time Complexity: O(n)
The process of converting the number to a digit array and traversing it (both for preparing maxIndexAfter and finding the swap position) each take O(n) time, linearly dependent on the number of digits (n).
Space Complexity: O(n)
The algorithm requires space proportional to the number of digits (n) for storing the digit array and the maxIndexAfter array, leading to O(n) space complexity.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)